import java.util.HashSet;
import java.util.Set;

/**
 * Created by L.jp
 * Description:你有一套活字字模 tiles，其中每个字模上都刻有一个字母 tiles[i]。返回你可以印出的非空字母序列的数目。
 *
 * 注意：本题中，每个活字字模只能使用一次。
 * User: 86189
 * Date: 2021-11-27
 * Time: 22:47
 */
public class Printing {
    Set<String> retSet=new HashSet<>();//存储最终的结果集合
    public  void  dfs(int[] visit,StringBuilder curStr,String tiles){
        //进来后先添加到set中,其中第一次进来添加的是空字符串
        retSet.add(curStr.toString());//dfs进来只做一件事，那就是把符合条件的临时字符串添加到set中，还可以达到去重操作
        for(int i = 0;i < tiles.length();i++) {//每次进行拼接的时候都要从第一个下标开始，因为不同位置的字符拼接的结果不同
            if (visit[i]==0) {//如果当前下标的元素没有被用过
                //回溯的过程
                visit[i] = 1;//那么接下来要把它拼接，所以先设置为1，用过
                curStr.append(tiles.charAt(i));//拼接
                dfs(visit, curStr, tiles);//添加到set
                curStr.deleteCharAt(curStr.length() - 1);//当第一次拼接判断完后，会退出for循环，来到第二个字符的判断开始新一轮的拼接，需要先把最后一个字符去掉再拼接
                visit[i] = 0;//因为第一次用的时候标记为用过，所以在之后的拼接判断的时候又需要置为0，表示没有用过
            }
        }
    }
    public   int numTilePossibilities(String tiles){
            //用一个数组来记录是否访问过这个位置
            int[] visit = new int[tiles.length()];
            dfs(visit,new StringBuilder(),tiles);
            return retSet.size()-1;
    }
}